1.Основные понятия интеллектуального анализа данных
1.1 Основные положения и определения
Понятие «интеллектуальный анализ данных» (ИАД) имеет множество
синонимов:
добыча данных;
извлечение информации;
раскопка данных;
интеллектуальный анализ данных;
средства поиска закономерностей;
извлечение знаний;
анализ шаблонов;
«извлечение зёрен знаний из гор данных»;
раскопка знаний в базах данных;
информационная проходка данных;
«промывание» данных;
обнаружение знаний в базах данных.
Однако наиболее известным из всех перечисленных является «добыча
данных» -дословный перевод английского словосочетания «DataMining».
Хотя корректнее говорить, что интеллектуальный анализ данных является
синонимом DataMining, учитывая происхождение этого термина и
направления (технологии), которое он обозначает. Возникновение всех
указанных терминов связано с новым витком в развитии средств и методов
обработки данных. До начала 90-х годов прошлого века, казалось, не было
особой нужды переосмысливать ситуацию в этой области. Все шло своим
чередом в рамках направления, называемого прикладной статистикой.
Теоретики проводили конференции и семинары, писали внушительные
статьи и монографии, изобиловавшие аналитическими выкладками. Вместе с
тем, практики всегда знали, что попытки применить теоретические экзерсисы
2
для решения реальных задач в большинстве случаев оказываются
бесплодными. Но на озабоченность практиков до поры до времени можно
было не обращать особого внимания -они решали, главным образом, свои
частные проблемы обработки небольших локальных баз данных.
В основу современной технологии DataMining (discovery-driven datamining)
положена концепция шаблонов (паттернов), отражающих фрагменты
многоаспектных взаимоотношений в данных. Эти шаблоны представляют
собой закономерности, свойственные подвыборкам данных, которые могут
быть компактно выражены в понятной человеку форме. Поиск шаблонов
производится методами, не ограниченными рамками априорных
предположений о структуре выборки и виде распределений значений
анализируемых показателей. Примеры заданий на такой поиск при
использовании Data Mining приведены в табл.1.
Таблица 1 – Сравнение OLAP и ИАД.
OLAP
ИАД
Каковы средние показатели
травматизма для курящих и
некурящих?
Встречаются ли точные шаблоны в
описаниях людей, подверженных
повышенному травматизму?
Каковы средние размеры счетов
существующих клиентов в сравнении
со счетами бывших клиентов
(отказавшихся от услуг
телекоммуникационной компании)?
Имеются ли характерные портреты
клиентов, которые, по всей
вероятности, собираются отказаться
от услуг телекоммуникационной
компании?
Какова средняя величина ежедневных
покупок по украденной и не
украденной кредитной карте?
Существуют ли стереотипные схемы
покупок для случаев мошенничества с
кредитными картами?
3
Важное положение ИАД -нетривиальность разыскиваемых шаблонов.
Это означает, что найденные шаблоны должны отражать неочевидные,
неожиданные (unexpected) регулярности в данных, составляющие так
называемые скрытые знания (hidden knowledge). К обществу пришло
понимание того, что сырые данные (raw data) содержат глубинный пласт
знаний, при грамотной раскопке которого могут быть обнаружены настоящие
самородки (рисунок 1).
Рисунок 1 ― Уровни знаний, извлекаемых из данных
Эволюционные алгоритмы
Первые случаи применения генетических алгоритмов находят в
образцах, возраст которых более 1 млрд. лет. Конечно же, речь идёт о живых
организмах, исследование процессов размножения которых и позволило
разработать данный алгоритм глобальной оптимизации.
Первой ласточкой, послужившей предвестницей применения
естественных алгоритмов в повседневной деятельности человека, явилась
работа Чарльза Дарвина «Происхождение видов», написанная в 1859 году.
Именно в этой работе чётко обозначены три столпа, на которых зиждятся
современные генетические алгоритмы, -наследственность, изменчивость и
отбор. Однако, если отбор -процесс отбраковки нежизнестойких видов, в
общем-то был понятен, то механизм, который отвечал за сохранение в
4
потомках черт предков и обеспечивал способность к приспособлению под
новые условия окружающей среды, стал понятен гораздо позднее -в 1944 году
О. Эйвери, К. Маклеод и М. Маккарти опубликовали результаты своих
исследований, доказывавших, что за наследственные процессы ответственна
«кислота дезоксирибозного типа». Однако о том, как работает ДНК, весь мир
узнал ещё позднее -27 апреля 1953 года в номере журнала «Nature» вышла
статья Уотсона и Крика, впервые предложивших модель двуцепочечной
спирали ДНК.
Раскрытие механизмов, отвечающих за создание и работу таких
сложных систем, как живые организмы, конечно же вдохновило многих
исследователей на моделирование этих процессов при помощи компьютеров.
В настоящее время существует огромное количество различных алгоритмов, в
той или иной степени моделирующих естественные процессы. При всей
разнице в подходах каждая из «школ», взяв за основу ряд принципов,
существующих в природе, упростила их до такой степени, чтобы их можно
было реализовать на компьютере.
Из основных особенностей эволюционных алгоритмов можно отметить
их некоторую сложность в плане настройки основных параметров
(вырождение либо неустойчивость решения). Поэтому, экспериментируя с
ними и получив не очень хорошие результаты, попробуйте не объявлять сразу
алгоритм неподходящим, а попытаться опробовать его при других настройках.
Данный недостаток следует из основной эвристики -можно «уничтожить»
предка самого лучшего решения, если сделать селекцию слишком «жёсткой»
(не зря ведь биологам давно известно, что если осталось меньше десятка
особей исчезающего вида, то этот вид сам по себе исчезнет из-за вырождения).
Генетические алгоритмы
Генетический алгоритм (ГА) является самым известным на данный
момент представителем эволюционных алгоритмов. ГА представляет собой
5
модель размножения живых организмов. Для начала представим себе целевую
функцию от многих переменных, у которой необходимо найти глобальный
максимум или минимум: 𝑓(𝑥1, 𝑥2, 𝑥3… , 𝑥𝑁).
Для того, чтобы заработал ГА, нам необходимо представить
независимые переменные в виде хромосом -цепочек символов, с которыми и
работает ГА.
На первом шаге необходимо преобразовать независимые переменные в
цепочки бит, которые будут содержать всю необходимую информацию о
каждой создаваемой особи. Имеется два варианта кодирования параметров:
в двоичном формате;
в формате с плавающей запятой.
Как было установлено на практике, более хорошие результаты даёт
вариант представления в двоичном формате.
Упрощённый алгоритм работы ГА.
В общем случае генетический алгоритм работает следующим образом.
В первом поколении все хромосомы генерируются случайно. Определяется их
«полезность». Начиная с этой точки, ГА может начинать генерировать новую
популяцию. Обычно размер популяции постоянен. Репродукция состоит из
двух шагов:
1. Селекции.
2. Генетических операторов (порядок применения не важен), из которых
самыми важными и принципиально необходимыми являются:
кроссовер(скрещивание)и мутация.
Селекция состоит в выборе хромосом, представляющих наибольшую
ценность в данном случае.
6
Кроссовер является наиболее важным генетическим оператором. Он
генерирует новую хромосому, объединяя генетический материал двух
родительских. Существует несколько вариантов кроссовера. Наиболее
простым является одноточечный. В этом варианте просто берутся две
хромосомы и перерезаются в случайно выбранной точке. Результирующая
хромосома получается из начала одной и конца другой родительских
хромосом.
Процедура взаимодействия инженера по знаниям с экспертом
Известен парадоксальный факт Джонсона о том, что по мере накопления
опыта специалист-эксперт все больше утрачивает умение словесно выражать
свои знания. Имеются достаточно убедительные психологические
доказательства того, что люди далеко не всегда в состоянии достоверно
описать свои мыслительные процессы. Теоретик искусственного интеллекта
М. Минский писал, что «самосознание — это сложная, но тщательно
сконструированная иллюзия...» и что «...только как исключение, а не как
правило, человек может объяснить то, что он знает».
Другое психологическое положение состоит в том, что опыт эксперта —
это интуиция, которая трудно поддаётся выражению в форме правил типа
«ЕСЛИ -ТО». Существует высказывание: «Кто скажет, тот не знает, кто знает,
тот не скажет».
Тем не менее, инженерия знаний предлагает определённые методы
(приёмы, способы) работы с экспертами. Эти методы направлены на
«раскручивание» лабиринтов памяти экспертов, в которых хранятся знания,
часто имеющие невербальный характер.
Классификация методов работы с экспертами
Под коммуникативными методами понимают все виды контактов
инженера по знаниям с живым источником знаний -экспертом. Среди этих
методов выделяют две большие группы: активные и пассивные.
7
Пассивные методы подразумевают, что ведущая роль в процедуре
извлечения знаний принадлежит эксперту. При этом инженер по знаниям
главным образом протоколирует рассуждения и действия эксперта.
В активных методах инициатива полностью в руках инженера по
знаниям. Он ведёт с экспертом беседу, предлагает различные «игры»,
организует «круглый стол» и т. д.
Пассивные методы на первый взгляд просты. Вместе с тем, они требуют
от инженера по знаниям умения анализировать «поток сознания» эксперта и
выделять в нем ценные фрагменты знания. Активные методы разделяют на две
группы в зависимости от числа экспертов, участвующих в процедуре
извлечения знаний. В групповых методах большое значение имеет дискуссия
между экспертами, в которой нередко выявляются нетривиальные аспекты
знаний. В то же время, ведущую роль на сегодняшний день играют
индивидуальные методы. В значительной степени это связано с
деликатностью процедуры «отъёма знаний», рисунок 2.
Рисунок 2 ― Классификация методов работы с экспертами
8
Структурирование знаний
Проблема структурирования знаний тесно связана с проблемой
извлечения, но рассматривается как бы под другим углом зрения. Вопрос
заключается не в том, как надо взаимодействовать с экспертом, а в том, что
надо получить в результате такого взаимодействия и что конкретно построить
для решения данной задачи.
Структурирование знаний иногда называют также концептуальным
анализом знаний.
Целью концептуального анализа знаний является построение модели
предметной области, которая представляет собой проблемно-
ориентированные и системно-независимые структуры.
Любая модель предметной области включает в себя систему понятий,
семантические отношения и стратегии принятия решений.
Система понятий
Под системой понятий подразумевают совокупность единиц смысловой
информации, отражающих реальные явления, процессы, факты, объекты и т.
д. предметной области. Инженерия знаний предлагает ряд практических
методов работы с экспертами для формирования системы понятий:
метод локального представления;
метод вычисления коэффициента использования;
метод формирования перечня понятий;
составление списка элементарных действий;
составление оглавления учебника;
текстологический метод.
Цель этих методов заключается в том, чтобы сформировать систему
понятий, обладающую свойствами полноты, уникальности, достоверности и
непротиворечивости.
9
Метод локального представления
При построении системы понятий с помощью метода локального
представления эксперта просят разбить задачу на подзадачи для перечисления
целевых состояний описания общих категорий цели. Далее для каждого
разбиения (локального представления) эксперт формулирует
информационные факты и даёт им чёткое наименование (название).
Считается, что для успешного решения задачи построения модели предметной
области число информационных фактов в каждом локальном представлении,
которыми человек способен одновременно манипулировать, должно быть
примерно равно семи.
Метод вычисления коэффициента использования
Этот метод основан на следующей гипотезе. Информационный факт
может являться понятием, если:
1) Он используется в большом числе подзадач;
2)Используется вместе с большим числом других информационных
фактов;
3)Редко используется совместно с другими информационными фактами
по сравнению с общим числом его использования во всех подзадачах (это и
есть коэффициент использования). Полученные значения коэффициента
использования служат критерием для классификации информационных
фактов и, таким образом, для формирования системы понятий.
Метод формирования перечня понятий
Данный метод заключается в том, что экспертам (желательно, чтобы их
было больше двух) даётся задание составить список понятий, относящихся к
исследуемой предметной области. Понятия, выделенные всеми экспертами,
включаются в систему понятий, остальные подлежат обсуждению.
Метод составления списка элементарных действий
10
Здесь эксперту даётся задание составить список элементарных действий
при решении задачи в произвольном порядке.
Метод составления оглавления учебника
В данном случае эксперту предлагается представить ситуацию, в
которой его попросили написать учебник. Необходимо составить на бумаге
перечень предполагаемых глав, разделов, параграфов, пунктов и подпунктов
книги.
Текстологический метод
Этот метод формирования системы понятий заключается в том, что
эксперту даётся задание выписать из руководств (книг по специальности)
некоторые элементы, представляющие собой единицы смысловой
информации.
1.2. Случайный лес и его спецификации
Что такое случайный лес?
Случайный лес–это одна из самых мощных, полностью автоматических
техник машинного обучения. Она почти не требует предобработки данных или
предварительного моделирования, но при этом позволяет получать очень
эффективные модели. Случайный лес создан на основе деревьев решений
(алгоритм CART).
Random forest (случайный лес)-алгоритм машинного обучения,
предложенный Лео Брейманоми Адель Катлер, заключающийся в
использовании комитета (ансамбля) решающих деревьев. Алгоритм сочетает
в себе две основные идеи: метод бэггинга Бреймана, и метод случайных
подпространств, предложенный Tin Kam Ho. Алгоритм применяется для задач
классификации, регрессии и кластеризации. (wiki)
11
В дальнейшем работа над алгоритмом была продолжена. Алгоритм
становился всё более совершенным. В настоящее время появились разные
версии. Разработчики продолжают совершенствовать алгоритм.
Случайный лес может использоваться для прогнозирования значений
непрерывных переменных. Например, продаж товаров в интернет-магазине.
Случайный лес может работать и с категориальными переменными.
Количество значений, которые может принимать переменная, не
ограничивается, но, как показывает практика, оно, в основном, не превышает
8. Случайный лес–это «коллекция» деревьев решений, которые используются
(вместе) для прогнозирования и глубокого изучения структуры данных. Самая
первая версия алгоритма Бреймана называлась бэггер (bagger)
Бэггинг (Bagging)
Метод формирования ансамблей классификаторов с использованием
случайной выборки с возвратом или бутстрепа. Название метода произошло
от англ. Bootstrap aggregating–bagging. Он был предложен в 1994 году Лео
Брейманом (LeoBreiman).
При формировании бутстрэп-выборок берётся множество данных, из
которого случайным образом отбирается несколько подмножеств, которые
содержат такое же количество примеров, как и исходное. Но поскольку отбор
производится случайно, набор примеров в этих выборках будет различным:
некоторые из них могут быть отобраны по несколько раз, а другие –ни разу.
Затем на основе каждой строится классификатор и их выходы комбинируются
(агрегируются) путем голосования или простого усреднения. Ожидается, что
результат будет намного точнее любой одиночной модели, построенной на
исходном наборе данных.
Бутстрэп (Bootstrap, Выборка с возвратом, Выборка с замещением)
12
Метод формирования нескольких выборок данных того же размера, что
и исходная генеральная совокупность, но с разными распределениями
интересующей величины. Бутстрэп был предложен в 1977 году Б. Эфроном.
Этот метод представляет разновидность рандомизированной обработки
данных.
Предполагается, что множество данных содержит N наблюдений,
образующих генеральную совокупность, из которой извлекаются выборки N с
равными вероятностями (1/N) для каждого наблюдения. Всего получают K
выборок, по каждой из которых оценивается интересующий параметр
исследуемой величины. Затем полученные оценки усредняются.
В Data Mining бутстреп используется с целью формирования
независимых выборок данных для обучения нескольких моделей, обычно
объединяемых в ансамбль, или для получения более достоверной ошибки
одной. Пусть имеется набор данных, содержащий m примеров. Тогда с
помощью бутстрепа можно сформировать ряд выборок, также содержащих m
примеров, но отобранных в случайном порядке. При этом каждая из них может
быть извлечена несколько раз. Следовательно, одни примеры могут оказаться
многократно продублированы, а другие –не появиться ни разу. Таким образом,
полученные с помощью бутстрэпа подмножества, скорее всего, будут иметь
различное распределение данных, что позволит обеспечить независимое
обучение некоторого количества моделей на единственном наборе.
Ансамбли моделей, построенные на бутсрэп-выборках, во многих
случаях позволяют улучшить точность классификации по сравнению с
одиночными. Кроме этого, если обучить одну и ту же модель на нескольких
таких выборках и усреднить полученные ошибки, то средняя будет более
достоверной оценкой ее точности.
Ансамбль моделей (Ensemble of models)
13
Набор моделей, используемых для решения единственной задачи. В
большинстве случаев применение ансамблей позволяет повысить точность и
достоверность результатов.
Существует две основные методики построения ансамблей –бустинг и
бэггинг. В бустинге формируется цепочка моделей, при этом каждая
следующая обучается на примерах, на которых предыдущая допустила
ошибку. Бэггинг реализует параллельное обучение на нескольких различных
выборках одинакового размера, полученных путем случайного отбора
примеров из исходного набора данных.
Дополнение
Создадим случайную выборку из базы данных и построим на её основе
дерево решений. Такая выборка, обычно, содержит половину исходного
набора данных и записи, её составляющие, могут быть любыми (из исходного
набора).
Повторим эту операцию. Создадим вторую случайную выборку и
построим дерево на её основе. Прогноз, сформированный этим деревом, будет,
как правило, отличным (хоть чуть-чуть) от первого.
Продолжим создавать деревья вышеописанным способом. Каждое из
них будет создано на слегка отличном от других наборе и будет выдавать
слегка отличающиеся от других прогнозы. Сей процесс может продолжаться
бесконечно, но, достаточно часто, строят от 200 до 500 деревьев. Тем не менее,
их количество может сильно отличаться от приведённых чисел. Всё зависит от
конкретной ситуации.
Как уже было сказано ранее, каждое из построенных деревьев
формирует свой прогноз.
Чтобы скомбинировать все эти отдельные прогнозы, используют
усреднение или голосование (voting).
14
Для прогнозирования объёмов продаж, используют усреднение
прогнозов деревьев решений.
Для работы с категориальными переменными используют голосование.
Например, наша целевая категориальная переменная –«пол». Принимает два
значения. При помощи голосования подсчитывается, какой процент деревьев
«проголосовали» своими прогнозами за «пол = мужской», а сколько за «пол =
женский». И таким образом определяется решение-«победитель». Описанный
процесс –бэггер.
Рандомизация
Главная идея Бреймана –использовать рандомизацию не только при
формировании выборок, но и непосредственно при создании деревьев.
При создании дерева, обычно выполняется полный поиск по всем
возможным предикторам для нахождения лучшего разбиения данных в
каждом узле дерева. Предположим, что вместо того, чтобы каждый раз
выбирать лучшее разбиение, мы выбираем разбиение случайным образом. Это
послужит гарантией того, что различные деревья будут отличаться друг от
друга.
Насколько рандомным должен быть случайный лес?
Если мы будет выбирать каждое разбиение случайным образом, то
получим полностью случайное дерево. Что, как правило, не очень хорошо.
Более разумным будет сначала выбрать случайным образом
подмножество кандидатов-предикторов, а потом разбивать, выбирая лучшее
разбиение из доступных.
Если у нас есть 1000 предикторов, можно выбрать набор из 30 в каждом
узле, а потом разделить, используя лучший предиктор из 30, вместо лучшего
из 1000.
15
Начинающие часто полагают, что мы выбираем случайный набор
предикторов единожды в начале анализа и потом выращиваем всё дерево,
используя только его.
Случайный лес работает не так. В Случайный лес мы выбираем новый
случайный набор предикторов в каждом узле дерева. Т.е., в каждом узле будет
свой набор предикторов (хотя, повторения возможно; естественно, всё зависит
от исходного объёма предикторов и величины случайного множества).
Чем больших размеров достигает дерево, тем больше вероятность того,
что на него окажут влияние большее число предикторов.
Управление уровнем рандомности
Если мы всегда производим поиск по всем предикторам во всех узлах
дерева, -то мы строим классические бэггерные модели; как правило, они
обладают ничем не выдающейся производительностью (качеством,
эффективностью).
Модели, обычно, становятся более эффективными, если мы производим
поиск не по всем переменным в каждом узле, ограничивая внимание к
случайному набору.
Выбрать количество переменных –это главное в управлении. Нужно
поэкспериментировать, что остановиться на оптимальном числе. Брейман
предлагал начать с квадратного корня от количества предикторов. Одной
переменной, почти всегда, оказывается совершенно недостаточно (низкая
эффективность модели), но 2 или 3, в то же время, часто дают впечатляющий
результат.
Сколько предикторов в узле?
В таблице 2 указана информация от Бреймана и Катлер (Cutler).
16
Таблица 2― Расчет предикторов.
Кол-во
предикторов
кв корень
0.5*кв
корень
2*кв
корень
ln2
100
10
5
20
6
1000
31
15,5
62
9
10000
100
50
200
13
100000
316
158
632
16
1000000
1000
500
2000
19
Конечно, имеет смысл поэкспериментировать и с другими значениями.
Выбранное значение является одинаковым для всего леса, для каждого узла.
Случайный лес. Прогнозирование
Прогнозирование в случайном лесу выполняется так же, как и в случае
бэггера –усреднением или голосованием.
Если нужно, то можно получить прогноз каждого дерева и сохранить его
в базу данных или в таблицу.
После этого можно самостоятельно рассчитать средневзвешенные
значения или использовать вариативность одиночных предикторов дерева.
Например, запись, для которой прогнозируется значение объёма продаж,
с большей вероятность будет –от дерева к дереву –иметь примерно
одинаковые значения прогнозируемого показателя при большом разнообразии
предикторов в зависимости от дерева. Так что проще всего поручить всю
работу случайному лесу, -чтобы он сохранял окончательные прогнозы.
Out Of Bag (holdout) –не все данные попадут в выборку.
17
Если мы делаем выборку из обучающего набора данных до
выращивания дерева, то в этом случае мы автоматически получаем
неучтённые (holdout) данные (для данного дерева).
В случайном лесу такие данные называются «выпавшие» (не в мешке,
Out Of Bag, OOB) данные. Собственно, не важно, как их называют.
Каждое дерево имеет свою holdout-выборку, ассоциированную с ним,
поскольку каждое дерево имеет отличную от других обучающую выборку.
Другими словами, каждая запись в главной базе данных будет «в мешке»
(inbag) для одних деревьев (будет входить в состав обучающей выборки), а для
других –«выпавшей», «не в мешке» (outofbag) (не будет входить в состав
обучающей выборки).
Случайный лес и сегментация
Ещё один из краеугольных камней в случайном лесу–«близость» или
соседство между записями в данных.
Допустим, из базы данных выбраны две записи. Мы хотим узнать,
насколько они похожи. «Пробегитесь» (dropdown) этими записями по каждому
дереву и посмотрите, «прибегут» ли они в один и тот же лист (terminalnode)?
Подсчитайте количество совпадений (2 в одном листе) и поделите на
число задействованных в «пробежках» деревьев.
Пропущенные значения
Классический случайный лес предлагает два подхода к обработке
пропущенных значений. Наиболее простой из них –заполнить пропущенные
значения средними или наиболее часто встречающимися значениями (для
категориальных переменных).
18
В таком случае, например, все записи с отсутствующим значением
возраста, будут заполнены одинаковыми средними значениями (везде будет
одно и то же число).
Несмотря на свою простоту, этот метод работает неожиданно хорошо
из-за огромного числа рандомизаций и усреднений в лесу.
Значимость переменных
Случайный лес содержит инновационный метод измерения
относительной значимости предиктора. Метод основан на измерении ущерба,
который будет нанесён нашей прогностической модели, если мы потеряем
доступ к данной переменной.
Чтобы имитировать такую ситуацию, мы случайно перемешиваем
значения в данных. Т.е., мы переставляем значения из одной строки в другую.
За раз мы перемешиваем значения только одного предиктора, а потом
измеряем потери в прогностической точности.
Случайный лес: достоинства и недостатки
Случайный лес имеет очень мало параметров для настройки
Самые важные: количество предикторов, используемых при разделении
узла и количество создаваемых деревьев.
При решении задачи классификации мы получим наилучшие
результаты, если выращиваем каждое дерева до максимального размера.
При прогнозировании значений непрерывных переменных, может
понадобиться настроить размер листа, чтобы ограничить размер деревьев.
Недостатки Модели
достигают наилучших результатов, когда деревья вырастают до очень
больших размеров. Грубо говоря, если у Вас в обучающей выборке N записей,
то дерево может разрастись до N/2 узлов.
19
1000000 записей –дерево из 500000 листьев (не узлов, а только листьев!).
500 таких деревьев –250 млн. листьев и 500 млн. узлов всего. Каждый
узел принимает участие в работе модели.
Случайный лес очень хорошо подходит для анализа данных сложной
структуры, содержащих, потенциально, миллионы столбцов, но умеренное
количество строк.
Краткий обзор алгоритма k-средних (k-means)
При большом количестве наблюдений иерархические методы
кластерного анализа не пригодны. В таких случаях используют
неиерархические методы, основанные на разделении, которые представляют
собой итеративные методы дробления исходной совокупности. В процессе
деления новые кластеры формируются до тех пор, пока не будет выполнено
правило остановки.
Такая неиерархическая кластеризация состоит в разделении набора
данных на определенное количество отдельных кластеров. Существует два
подхода. Первый заключается в определении границ кластеров как наиболее
плотных участков в многомерном пространстве исходных данных, т.е.
определение кластера там, где имеется большое «сгущение точек». Второй
подход заключается в минимизации меры различия объектов.
Общие сведения
Наиболее распространен среди неиерархических методов алгоритм k-
средних, также называемый быстрым кластерным анализом. Полное описание
алгоритма можно найти в работе Хартигана и Вонга (Hartigan andWong, 1978).
В отличие от иерархических методов, которые не требуют предварительных
предположений относительно числа кластеров, для возможности
использования этого метода необходимо иметь гипотезу о наиболее вероятном
количестве кластеров.Алгоритм k-среднихстроит kкластеров, расположенных
20
на возможно больших расстояниях друг от друга. Основной тип задач, которые
решает алгоритм k-средних, -наличие предположений (гипотез) относительно
числа кластеров, при этом они должны быть различны настолько, насколько
это возможно. Выбор числа k может базироваться на результатах
предшествующих исследований, теоретических соображениях или интуиции.
Общая идея алгоритма: заданное фиксированное число k кластеров
наблюдения сопоставляются кластерам так, что средние в кластере (для всех
переменных) максимально возможно отличаются друг от друга.
Описание алгоритма
1.Первоначальное распределение объектов по кластерам.
Выбирается число k, и на первом шаге эти точки считаются «центрами»
кластеров. Каждому кластеру соответствует один центр.
Выбор начальных центроидов может осуществляться следующим
образом:
выбор k-наблюдений для максимизации начального расстояния;
случайный выбор k-наблюдений;
выбор первых k-наблюдений.
В результате каждый объект назначен определенному кластеру.
2. Итеративный процесс.
Вычисляются центры кластеров, которыми затем и далее считаются
покоординатные средние кластеров. Объекты опять перераспределяются.
Процесс вычисления центров и перераспределения объектов
продолжается до тех пор, пока не выполнено одно из условий:
кластерные центры стабилизировались, т.е. все наблюдения
принадлежат кластеру, которому принадлежали до текущей
итерации;
21
число итераций равно максимальному числу итераций.
На рис.6.1приведен пример работы алгоритма k-средних для k, равного
двум.
Рисунок 3 ― Пример работы алгоритма k-средних(k=2)
Выбор числа кластеров является сложным вопросом. Если нет
предположений относительно этого числа, рекомендуют создать 2 кластера,
затем 3, 4, 5 и т.д., сравнивая полученные результаты
22
Проверка качества кластеризации
После получений результатов кластерного анализа методом k-средних
следует проверить правильность кластеризации (т.е. оценить, насколько
кластеры отличаются друг от друга). Для этого рассчитываются средние
значения для каждого кластера. При хорошей кластеризации должны быть
получены сильно отличающиеся средние для всех измерений или хотя бы
большей их части.
Достоинства алгоритма k-средних:
простота использования;
быстрота использования;
понятность и прозрачность алгоритма.
Недостатки алгоритма k-средних:
алгоритм слишком чувствителен к выбросам, которые могут
искажать среднее. Возможным решением этой проблемы является
использование модификации алгоритма -алгоритм k-медианы;
алгоритм может медленно работать на больших базах данных.
Возможным решением данной проблемы является использование
выборки данных.
Байесовская классификация. Краткий обзор возможностей
Альтернативные названия: байесовское моделирование, байесовская
статистика, метод байесовских сетей.
Изначально байесовская классификация использовалась для
формализации знаний экспертов в экспертных системах, сейчас байесовская
классификация также применяется в качестве одного из методов Data Mining.
Так называемая наивная классификация или наивно-байесовский подход
(naive-bayes approach) является наиболее простым вариантом метода,
23
использующего байесовские сети. При этом подходе решаются задачи
классификации, результатом работы метода являются так называемые
«прозрачные» модели.
«Наивная» классификация -достаточно прозрачный и понятный метод
классификации. «Наивной» она называется потому, что исходит из
предположения о взаимной независимости признаков.
Свойства наивной классификации:
1. Использование всех переменных и определение всех зависимостей
между ними.
2. Наличие двух предположений относительно переменных:
все переменные являются одинаково важными;
все переменные являются статистически независимыми, т.е.
значение одной переменной ничего не говорит о значении
другой.
Большинство других методов классификации предполагают, что перед
началом классификации вероятность того, что объект принадлежит тому или
иному классу, одинакова; но это не всегда верно.
Допустим, известно, что определенный процент данных принадлежит
конкретному классу. Возникает вопрос, можем ли мы использовать эту
информацию при построении модели классификации? Существует множество
реальных примеров использования этих априорных знаний, помогающих
классифицировать объекты. Типичный пример из медицинской практики.
Если доктор отправляет результаты анализов пациента на дополнительное
исследование, он относит пациента к какому-то определенному классу. Каким
образом можно применить эту информацию? Мы можем использовать ее в
качестве дополнительных данных при построении классификационной
модели.
24
Метод «ближайшего соседа» или системы рассуждений на основе
аналогичных случаев. Краткий обзор возможностей
Следует сразу отметить, что метод «ближайшего соседа» («nearest
neighbour») относится к классу методов, работа которых основывается на
хранении данных в памяти для сравнения с новыми элементами. При
появлении новой записи для прогнозирования находятся отклонения между
этой записью и подобными наборами данных, и наиболее подобная (или
ближний сосед) идентифицируется.
Например, при рассмотрении нового клиента банка, его атрибуты
сравниваются со всеми существующими клиентами данного банка (доход,
возраст и т.д.). Множество "ближайших соседей" потенциального клиента
банка выбирается на основании ближайшего значения дохода, возраста и т.д.
При таком подходе используется термин «k-ближайший сосед» («k-
nearest neighbour»). Термин означает, что выбирается k «верхних»
(ближайших) соседей для их рассмотрения в качестве множества «ближайших
соседей». Поскольку не всегда удобно хранить все данные, иногда хранится
только множество "типичных" случаев. В таком случае используемый метод
называют рассуждением по аналогии (Case Based Reasoning, CBR),
рассуждением на основе аналогичных случаев, рассуждением по прецедентам.
Прецедент — это описание ситуации в сочетании с подробным
указанием действий, предпринимаемых в данной ситуации.
1.3. Многообразие сфер ИАД
Введение в SocialMining. Понятие социальной сети и её анализа
В жизни человека общество играет важную роль: с детства, находящиеся
рядом люди оказывают то или иное влияние на нас, происходит непрерывное
взаимодействие в социальной сфере (в детском саду, школе, университете,
дома, на работе), без которого полноценное развитие личности невозможно.
25
С середины прошлого века было опубликовано множество работ
ученых-социологов, в том числе и отечественных, где они предлагали
различные подходы анализа в сфере общественных отношений. В своих
трудах под социальной сетью они понимали структуры людей, связанных друг
с другом общими отношениями или интересами. Уже позднее, с появлением
Интернета, также стали называть специализированные электронные порталы,
о которых будет рассказано позже. Тем не менее понятие «социальная сеть»
имеет более широкий смысл. Социолог Градосельская Г. В. предложила
следующее определение.
Социальные сети — это особая реальность и особая философия анализа
данных, которая позволяет интегрировать различные математические
подходы статистические, системные, имитационные с современной
социальной теорией.
С развитием информационных технологий, а также сети Интернет,
взаимоотношения между людьми перешли на новый уровень. Появились
электронные порталы, способные отражать те или иные стороны активности
человека в обществе, сохранять и накапливать информацию. Особое место
занимают виртуальные социальные сети, например, такие как «Вконтакте» и
другие.
Наряду с этим всегда сохранялось желание понять сущность
происходящих в обществе процессов для осуществления более эффективного
контроля и управления ими. Таким образом, сложились предпосылки для
анализа данных из социальных сетей.
Social Mining-применение методов и алгоритмов Data Mining для поиска
и обнаружения зависимостей и знаний в социальных сетях. Наиболее часто
используемое средство для анализа и визуализации в данной области –это
граф, где узлами (акторами) являются люди или группы, а дуги
26
демонстрируют взаимоотношения (связи) или потоки информации между
узлами.
Виртуальная социальная сеть
Под виртуальной социальной сетью понимается социальная структура
Интернет-среды, узлы которой составляют организации или отдельные люди,
а связи обозначают установленные взаимодействия (политические,
корпоративные, служебные, семейные, дружеские, по интересам). Формально
данные сети представлены в виде специально разработанных электронных
порталов, таких как «Одноклассники», «Вконтакте» и других.
Сразу после регистрации нового участника создается профиль
пользователя, в котором изначально содержится информация из заполненных
анкетных данных: возраст, пол, семейное положение, интересы, образование
и прочее. Этот профиль более «развитый» по сравнению с аналогами в блогах
и форумах, так как последние могут быть частью средств общения в
социальной сети.
Попадая в виртуальную социальную сеть, человек начинает поиски
знакомых или интересных ему людей для общения. Однако нередко
возникают ситуации, когда сразу после регистрации участник некоторое время
не проявляет активности. На самом деле такое часто бывает и в обычной
жизни, когда человек, оказываясь в новом коллективе, поначалу несколько
замкнут и не разговорчив. Спустя время происходит освоение в обществе, и
эти комплексы пропадают.
Внутри социальной сети образуются различные группы и сообщества по
интересам, например, любителей музыки, автомобилей, учебы, работы. Связи
между участниками таких объединений довольно сильные, что позволяет их
легко идентифицировать. Рассмотрим рис.10.3, где изображен пример
описанной ситуации. Внутри группы между участниками связей больше, и они
сильнее, чем с другими членами социальной сети. В составе сообществ могут
27
появляться подгруппы и подсообщества, таким образом образуя иерархию (на
рис.4 такое можно наблюдать в группе 1).
Рисунок 4 ― Группы внутри социальной сети
В процессе «сетевой жизни» участник пополняет свой профиль новой
информацией. Это могут быть данные о его друзья, группах, встречах,
сообщениях, комментариях.
Какие инструменты общения используются в них? Блог -сетевой
журнал, основным содержимым которого являются регулярно добавляемые
записи. Отличия блога от традиционного дневника обусловливаются средой:
они обычно публичны и предполагают сторонних читателей, которые могут
вступить в публичную полемику с автором.
Чат предоставляет возможность обмена текстовыми сообщениями
между несколькими участниками в режиме online. Пользователь форума
может создавать новую «тему», доступную для других. Другие пользователи
могут просматривать ее и оставлять свои комментарии в режиме
последовательной записи.
Вики-справочники -веб-сайты, содержимое которых может
редактироваться посетителями сайта.
28
Online игры получили также широкое распространение в социальных
сетях и их можно рассматривать в качестве одного из видов взаимодействия
людей в сети.
Виртуальная социальная сеть рассматривается также как социально
значимый объект, который способен влиять на общество.
Для решения каких задач может помочь Social Mining?
Введение в Web Mining. Основные понятия и принципы
Web Mining -применение методов и алгоритмов Data Mining для
обнаружения и поиска зависимостей и знаний в сети Интернет.
Таблица 3— Основные термины и понятия web mining.
Название
Электронный
портал
Веб-сервер
Веб-лог
Веб-контент
Веб-структура
29
Продолжение таблицы 3.
Обобщённые ассоциативные правила
Методы поиска обобщенных правил при вычислении используют
информацию о группировке элементов (таксономию), что позволяет
значительно расширить круг задач, решаемых алгоритмами поиска
ассоциативных правил. Примером обобщенного ассоциативного правила
может служить высказывание: «Если человек купил Ряженку, то он, скорее
всего, купит товар из группы Хлебобулочные изделия».
Алгоритм поиска ассоциативных правил FPG
Протокол
IP-адрес
Идентификация
Авторизация
Клиент
Гиперссылка
30
Узким местом в алгоритме Apriori является процесс генерации
кандидатов в популярные предметные наборы. Например, если база данных
транзакций содержит 100 предметов, то потребуется сгенерировать
2100~1030кандидатов. Таким образом, вычислительные и временные затраты,
которые нужны на их обработку, могут быть неприемлемыми. Кроме этого,
алгоритм Apriori требует многократного сканирования базы данных
транзакций, а именно столько раз, сколько предметов содержит самый
длинный предметный набор. Поэтому был предложен ряд алгоритмов,
которые позволяют избежать генерации кандидатов и сократить требуемое
число сканирований набора данных.
Одной из наиболее эффективных процедур поиска ассоциативных
правил является алгоритм, получивший название Frequent Pattern-Growth
(FPG), что можно перевести как «выращивание популярных (часто
встречающихся) предметных наборов». Он позволяет не только избежать
затратной процедуры генерации кандидатов, но уменьшить необходимое
число проходов базы данных до двух.
1.4. Итоги исследования интеллектуального анализа данных
Человеческое общество на современном этапе развития становится всё
более сложным. Появляются новые задачи, проблемы, вызовы, которые
необходимо решать, чтобы прогресс не стоял на месте. Наука не стоит на
месте. Она предлагает более совершенные технологии, подходы, методики и
методы. Одним из таки направлений является искусственный интеллект.
Искусственный интеллект, на взгляд автора, можно считать новой
областью человеческих знаний, потому что границы её по-прежнему не
определены. Они продолжают активно расширяться. Это вызвано тем, что
данный подход оказался очень востребованным в современном обществе. При
этом с каждым днём открываются всё новые и новые направления, где он
оказывается очень полезным и, часто, просто незаменимым.
31
Как показывают исследования, технологии искусственного интеллекта
обладают неисчерпаемым потенциалом. Это однозначно указывает на то, что
работы в этом направлении представляются крайне перспективными.
Способствующим фактором является то, что для проведения научных
изысканий/разработок в данной области достаточно (минимально)
компьютера с доступом к глобальной сети. Благодаря таким невысоким
требованиям, круг потенциальных исследователей оказывается очень
широким. Им может стать почти каждый. Из этого следует, что учебные
материалы, знакомящие читателей с областью искусственного интеллекта, его
методами и задачами, для решения которых они могут применяться, являются
актуальными и востребованными.
Одной из технологий искусственного интеллекта, является
интеллектуальный анализ данных (datamining). Она получила широкое
распространение и используется в самых разных областях для решения
разнообразных задач. Перечень проблем, решаемых посредством методов
вышеприведённой технологии, регулярно пополняется.